// =====================================================================================
//
//       Filename:  antcolony.cpp
//
//    Description:  Implémentation des structures de données utilisées par l'algorithme
//					d'optimisation par simulation d'une colonie de fourmis
//
//        Version:  1.0
//        Created:  16/09/2009 17:51:00
//       Revision:  none
//       Compiler:  g++
//
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:
//
// =====================================================================================

#include	<cstdlib>
#include	<list>
#include	<vector>
#include	<cmath>
#include	<cfloat>
#include	"graphe.h"
#include	"antcolony.h"

/****************************************/
/* IMPLEMENTATION DE LA CLASSE ANTGRAPH */
/****************************************/
AntGraph::AntGraph(int n,double **distances) {
	for (int i=0;i<n;++i) sommets.push_back(new Sommet(i,""));
	for (int i=0;i<n;++i) {
		for (int j=0;j<n;++j) if (j!=i) {
			AntEdge *ae=new AntEdge(i*n+j,sommets[i],sommets[j],distances[i][j],"");
			sommets[i]->arcs.push_back(ae);
			arcs.push_back(ae);
		}
	}
}

list<Arc*> AntGraph::shortest_tour(int iterations,int nb_ants,Sommet *start,double alpha,double beta,double rho) {
	const int MAX_FAILURES=100;	//Nombre maximal de tentatives de passage d'une fourmi avant abandon
	list<Arc*> visited;	//Liste des arcs par lesquels la fourmi est passée
	vector<double> probas;	//Probabilités de passage sur les arcs voisins d'un sommet
	Sommet *current;	//Sommet courant où se trouve la fourmi
	bool stop=false;	//Condition d'arrêt, utilisée pour vérifier si aucun arc n'est accessible à partir du sommet courant
	double alea;	//Nombre aléatoire
	double proba;	//Fonction de répartition de la probabilité d'accès à l'un des arcs à partir du noeud courant
	double length;	//Longueur totale de l'itinéraire
	double minlength=DBL_MAX;	//Longueur minimale des itinéraires trouvés pendant la dernière itération, permet de repérer le meilleur trajet de la dernière itération
	Arc* newedge;	//Nouveau noeud choisi par la fourmi
	int nb_failures;	//Nombre d'échecs de passage de fourmis
	bool trapped;	//Indique si la fourmi est bloquée
	list<Arc*> result;	//Meilleure tournée
	/*cout << sommets.size() << " : ";
	for (vector<Sommet*>::iterator itt=sommets.begin();itt!=sommets.end();itt++) {
		cout << "(" << (*itt)->id << ") ";
	}
	cout << endl;
	cout << arcs.size() << " : " << endl;
	for (vector<Arc*>::iterator itt=arcs.begin();itt!=arcs.end();itt++) {
		cout << "(" << (*itt)->id << "," << (*itt)->orig->id << "," << (*itt)->dest->id << "," << (*itt)->poids << ") ";
	}
	cout << endl;*/
	for (vector<Arc*>::iterator itt=arcs.begin();itt!=arcs.end();itt++) ((AntEdge*)(*itt))->pheromones=1;
	for (int i=0;i<iterations;++i) {
		for (vector<Arc*>::iterator itt=arcs.begin();itt!=arcs.end();itt++) ((AntEdge*)(*itt))->add_pheromones=0;
		for (int j=0;j<nb_ants;++j) {
			stop=false;
			nb_failures=0;
			do {
				//Initialisation
				for (vector<Sommet*>::iterator itt=sommets.begin();itt!=sommets.end();itt++) (*itt)->statut=0;
				visited.clear();
				current=start;
				//Parcours aléatoire
				while (visited.size()<sommets.size()-1 && !stop) {
					current->statut=1;
//					cout << current->id << " : ";
//					for (list<Arc*>::iterator itt=current->arcs.begin();itt!=current->arcs.end();itt++) cout << (*itt)->id << " ";
					probas.clear();
					proba=0.0;
					trapped=true;
					for (list<Arc*>::iterator it=current->arcs.begin();it!=current->arcs.end();it++) {
//						cout << " " << (*it)->id;
						if (!((*it)->coupe) && (*it)->dest->statut==0) {
//							cout << "!";
							trapped=false;
							proba+=pow(((AntEdge*)(*it))->pheromones,alpha)*pow((*it)->poids,-beta);
						}
						probas.push_back(proba);
					}
					vector<double>::iterator itvv=probas.begin();
					if (trapped) stop=true; else {
//						cout << " -- ok";
						alea=proba*rand()/(double)RAND_MAX;
						list<Arc*>::iterator it=current->arcs.begin();
						for (vector<double>::iterator itv=probas.begin();itv!=probas.end() && alea>(*itv);itv++) it++;
						newedge=*it;
						visited.push_back(newedge);
						current=newedge->dest;
					}
//					cout << endl;
				}
			} while (stop && nb_failures++<MAX_FAILURES);
			if (stop) {	//Impossible de trouver un chemin
				visited.clear();
				return visited;
			}
			//Dépôt des phéromones sur le chemin du retour
			length=0;
			for (list<Arc*>::iterator it=visited.begin();it!=visited.end();it++) length+=(*it)->poids;	//Calcul de la longueur totale de la tournée
			for (list<Arc*>::iterator it=visited.begin();it!=visited.end();it++) ((AntEdge*)(*it))->add_pheromones+=1/length;	//Dépôt d'une quantité de phéromones inversement propotionnelle à la longueur de la tournée
			if (i==iterations-1 && length<minlength) {	//Si on est dans la dernière itération, il faut déterminer le meilleur chemin. Dans ce cas, si le chemin trouvé est meilleur que le chemin précédent le plus court, on le recopie dans le résultat.
				minlength=length;
				result=visited;
			}
		}
		for (vector<Arc*>::iterator it=arcs.begin();it!=arcs.end();it++) {
			AntEdge *ae=(AntEdge*)(*it);
			ae->pheromones+=ae->add_pheromones;	//Dépôt des phéromones
			ae->add_pheromones=0;
			ae->pheromones*=(1-rho);	//Evaporation
		}
	}
	//Reconstitution de la tournée optimale
	for (vector<Sommet*>::iterator itt=sommets.begin();itt!=sommets.end();itt++) (*itt)->statut=0;
	//_travel(sommets.size()-1,start,result);	//Reconstitution par recomposition d'une tournée à partir des arcs contenant le maximum de phéromones
	return result;
}

bool AntGraph::_travel(int size,Sommet *start,list<Arc*> &result) {
	if (size==0) return true;
	start->statut=1;
	bool found=false;
	bool trapped=false;
	while (!found && !trapped) {
		double max=DBL_MAX;	//Quantité de phéromones maximale recherchée sur les arcs voisins
		double min=-DBL_MAX;	//Quantité de phéromones maximale trouvée
		AntEdge *best=0;	//Meilleure arête trouvée, celle qui contient le plus de phéromones, mais pas au-delà de max
		for (list<Arc*>::iterator it=start->arcs.begin();it!=start->arcs.end();it++) {
			AntEdge *a=(AntEdge*)(*it);
			if (!a->coupe && a->dest->statut==0 && a->pheromones>min && a->pheromones<max) {
				min=a->pheromones;
				best=a;
			}
		}
		if (best==0) trapped=true; else {
			max=min;
			if (_travel(size-1,best->dest,result)) {
				result.push_front(best);
				found=true;
			}
		}
	}
	start->statut=0;
	return found;
}
